import java.util.*;

/**
 * 递归
 * 5 f(4)
 * 4 f(3)
 * 3 (f2)
 * 2 (f1)
 * 1 f(0)
 * f(0) 1
 * (f1) 2
 * (f2) 3
 * (f3) 4
 * (f4) 5
 */
public class Factorial {
    /**
     * 例1  P40：  递归阶乘
     * <p>
     * 用递归的方法求  阶乘
     * 阶乘的定义 n!= 1*2*3*(n-2)*(n-1)*n，其中n为自然数，当然 0!=1
     */
    public static int f(int n) {
        if (n == 1) {
            return 1;
        }
        return n * f(n - 1);
    }

    /**
     * 例2  P41:  递归反向打印字符串
     */
    public static void reversPrintString(int n, String str) {
        if (n == str.length()) {  //索引 每次n+1, 一直到 字符串长度为止
            return;
        }
        reversPrintString(n + 1, str);
        System.out.println(str.charAt(n));  //打印方法 写在 递归函数下面 就是逆序了， 写在递归函数前面 就是正序。
    }

    /**
     * 例3 P42 ：  使用 递归 进行二分查找
     */
    private static int binarySearchUseFactorial(int[] a, int target, int i, int j) {
        if (i > j) {
            return -1;
        }
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            return binarySearchUseFactorial(a, target, i, m - 1);
        } else if (target > a[m]) {
            return binarySearchUseFactorial(a, target, m + 1, j);
        } else {
            return m;
        }
    }

    public static int binarySearch(int[] a, int target) {
        return binarySearchUseFactorial(a, target, 0, a.length - 1);
    }


    /**
     * 例4 P43   递归冒泡排序
     *
     * @return
     */
    private static void bubble(int[] a, int j) {
        if (j == 0) {
            return;
        }
        int x = 0; //x是分割线，左边是未排序的，右边是已排序的
        for (int i = 0; i < j; i++) {
            if (a[i] > a[i + 1]) {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                x = i;
            }
        }
        bubble(a, x);
    }

    public static void bubbleSort(int[] a) {
        bubble(a, a.length - 1);
    }


    /**
     * 159264  -> 124569
     * 例5 P44  递归 插入排序     low 是 未排序段 的首个元素索引位置
     */
    public static void insertion(int[] a, int low) {
        if (low == a.length) {  //当未 排序 索引
            return;
        }
        int t = a[low];  //t 是 当前要插入的元素
        int i = low - 1; //i 是 分割点， i即i左边是排好序的， i右边是未排好序的
        while (i >= 0 && a[i] > t) {
            a[i + 1] = a[i];
            i--;
        }
        if (i + 1 != low) {
            a[i + 1] = t;
        }
        insertion(a, low);

    }

    /**
     * 例6
     * 递归- 斐波那契数列
     * [ 0                n = 0
     * f(n) ->[ 1                n = 1
     * [ f(n-1) + f(n-2)  n > 1
     * <p>
     * 斐波那契 递归 的时间复杂度主要取决于递归调用的次数 :  2*(fn+1)-1
     */
    public static int fibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int x = fibonacci(n - 1);
        int y = fibonacci(n - 2);
        return x + y;
    }
// 上面的算法会有很多重复的计算， 例如f(4) = f(3)+f(1) = f(2)+f(1)+f(1)= f(1) +(f0) +(f1) +f(1) 这里的f(1)算了3次，可以f(1)放到一个数组里，每次取就行了不需要重复计算

    /**
     * 例7
     * 对 递归-斐波那契数列 用记忆法进行优化， 就是将算过的f(n)放到数组里存起来，再次用的时候直接从数组里取即可
     */
    public static int fibonacciUseMemory(int n) {
        int[] cache = new int[n + 1];  //这里为什么是n+1, 是因为f(0)=0 f(1)=1 这是已知的要放到数组里的两个元素， 第n个元素刚好放到数组的索引是n，数组长度就是m+1
        Arrays.fill(cache, -1);  //将数组用-1填充满
        //先将0和1的值放入数组
        cache[0] = 0;
        cache[1] = 1;
        //调用递归
        return fibonacciUseMemoryInner(n, cache);
    }

    private static int fibonacciUseMemoryInner(int n, int[] cache) {
        //进来先判断数组是否已经有值，有值就直接返回
        if (cache[n] != -1) {
            return cache[n];
        }
        //仍然使用 f(n) = f(n-1) + f(n-2) 的函数
        int x = fibonacciUseMemoryInner(n - 1, cache);
        int y = fibonacciUseMemoryInner(n - 2, cache);
        //将本地计算的结果存放到cache数组里，方便下次直接获取使用
        cache[n] = x + y;
        return cache[n];
    }


    /**
     * 例8
     * 求 n 个 数的 和
     * 例如n=5   result= 5 + f(4) = 5 + 4 + f(3) = 5 + 4 + 3 + f(2) = 5 + 4 + 3 + 2 + 1
     */
    public static long sumUseFactorial(long n) {
        if (n == 1) {
            return 1;
        }
        return sumUseFactorial(n - 1) + n;     //这里当n=5时， result = 5 + f(4)
    }

    /**
     * 尾递归 可以避免爆栈问题
     * @param args
     */


    /**
     * 例9
     * 汉诺塔
     * a,b,c三个柱子，分别用三个linkedList创建，然后大的盘必须放在小的盘下面，
     *
     * @param args
     */
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();

    //a 柱子 初始化 数字大小代表圆盘大小
    private static void init(int n) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);
        }
    }

    public static void beginRemove() {
        init(3);
        soutABC();
        //将a的最上面的元素 移动到 b柱子上
        b.addLast(a.removeLast());
        soutABC();
    }

    /**
     * @param n 圆盘个数
     * @param a 源
     * @param b 借
     * @param c 目
     */
    static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        move(n - 1, a, c, b);
        c.addLast(a.removeLast());
        soutABC();
        move(n - 1, b, a, c);
    }

    private static void soutABC() {
        System.out.println("-----------");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }

    /**
     * 例10
     * 杨辉三角
     * 1
     * 1   1
     * 1   2   1
     * 1   3   3   1
     * 1   4   6   4   1
     * 1   5   10  10  5   1
     *
     * @param i 第i行 (i和j是从0开始的)
     * @param j 第j列
     */

    public static int pascalTriangle(int i, int j) {
        //每行第一列是1， 每行的最后一列是1
        if (j == 0 || j == i) {
            return 1;
        }
        return pascalTriangle(i - 1, j - 1) + pascalTriangle(i - 1, j);
    }

    //杨辉三角 打印前后空格  n代表高度，i代表行数(从0开始) ,  因为高度不一样 第一行需要加的空格个数也不一样
    public static void printSpace(int n, int i) {
        int num = (n - 1 - i) * 2;  //空格数量
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

    public static void printPascalTriangle(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.print(pascalTriangle(i, j) + "   ");
            }
            //换行
            System.out.println();
        }
    }

    /**
     * 杨辉三角  优化- 记忆法(二维数组)
     */
    public static int pascalTriangleUseMemory(int[][] cache, int i, int j) {
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        if (j == 0 || i == j) {  //每行第一列 和 最后一列 是1
            return 1;
        }
        cache[i][j] = pascalTriangleUseMemory(cache, i - 1, j - 1) + pascalTriangleUseMemory(cache, i - 1, j);
        return cache[i][j];
    }

    /**
     * 对外  杨辉三角  优化- 记忆法(二维数组)
     *
     * @param n
     */
    public static void printPascalTriangleUseMemory(int n) {
        //二维数组 存已经计算过的值
        int[][] cache = new int[n][];
        for (int i = 0; i < n; i++) {   //这里 i<n 不能加=号,因为i是从0开始的 例如高度n=5,i从0开始到4
            cache[i] = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                System.out.print(pascalTriangleUseMemory(cache, i, j));
            }
            System.out.println();
        }
    }


    /**
     * 杨辉三角 -- 动态规划
     */
    private static void createRow(int[] row, int i) {
        if (i == 0) {
            row[0] = 1;
            return;
        }
        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j-1];
        }
    }

    /**
     * 对外-  杨辉三角 动态规划
     */
    public static void printPascalTriangleUseDynamicProgram(int n){
        int[] row = new int[n];
        for(int i = 0 ; i < n ; i++){
            createRow(row,i);
            for(int j = 0 ; j<=i;j++){
                System.out.print(" "+row[j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(70, 70, -1, 5, 3, 3, 4, 4, 4, 4, 99);
        ArrayList<Integer> srcList = new ArrayList<>(list);
        ArrayList<Integer> newList = new ArrayList<>(list);
        for (int i = 0; i < newList.size() - 1; i++) {
            for (int j = newList.size() - 1; j > i; j--) {
                if (newList.get(i).equals(newList.get(j))) {
                    newList.remove(j);
                }
            }
        }
        System.out.println(newList);
    printPascalTriangleUseDynamicProgram(5);
    }
}
